題目連結: Linked List Cycle

題目描述為給定一個 Linked List 的 head，要我們判斷此 Linked List 是否有環(Cycle)。
題目的補充說明希望我們使用的記憶體空間複雜度為 O(1)。

思路 1 : Hash 法

我們可以把經過的節點都記錄起來，遍歷整個 Linked List ，若有 cycle 則會有重複經過的節點，此時返回 true。若都沒有重複經過的節點表示無 cycle。

• 複雜度評估
  當 Linked List 長度為 N 時，我們需要遍歷整個 Linked List 或經過重複節點 ，時間複雜度為 O(N)。此方法建立了 map 來紀錄經過的節點，空間複雜度為O(N)。

參考程式碼

func hasCycle(head *ListNode) bool {
    m := make(map[*ListNode]bool)
    for head != nil {
        if m[head] {
            return true
        }
        m[head] = true
        head = head.Next
    }
    return false
}

思路 2 : 快慢指針法

我們可以宣告兩個指針，慢的一次走一步，快的一次走兩步長，若 Linked List 有 cycle，則快的指針會與慢指針相遇，若沒有 cycle 則最終快的指針會先走完。需要留意的點為: 快指針一次走兩步長，我們要避免越界，此為迴圈停止條件。

• 複雜度評估
  當 Linked List 長度為 N 時，我們需要遍歷整個 Linked List 或碰到節點 ，時間複雜度為 O(N)。此方法並只用了常數個變數，空間複雜度為O(1)。

參考程式碼

func hasCycle(head *ListNode) bool {
	if head == nil {
		return false
	}

	slow, fast := head, head.Next

	for fast != nil && fast.Next != nil {
		if slow == fast {
			return true
		}
		slow = slow.Next
		fast = fast.Next.Next
	}

	return false
}

小結:

解法 1 空間複雜度為 O(N)，不滿足題目要求。
解法 2 為經典方法，有許多延伸題目，若是要求此 Linked List cycle 的起始點，可參考此連結。
我將解法程式碼上傳到此，因為此題需要實作 ListNode，我尚未加上測試過程。